package main

import (
	"fmt"
	"sync"
)

// 双端队列/双端列表

type DoubleList struct {
	head *ListNode   // 指向链表头部
	tail *ListNode   // 指向链表尾部
	len int			 // 双端列表长度
	lock sync.Mutex  // 为了进行并发安全Pop弹出操作
}

// ListNode 列表节点
type ListNode struct {
	pre *ListNode   // 前驱节点
	next *ListNode  // 后继节点
	value string    // 值
}

// GetValue 获取节点值
func(node *ListNode) GetValue() string {
	return node.value
}

// GetPre 获取当前节点的前驱节点
func (node *ListNode) GetPre() *ListNode {
	return node.pre
}

// GetNext 获取当前节点的后继节点
func (node *ListNode) GetNext() *ListNode {
	return node.next
}

// HashPre 判断当前节点是否存在前驱节点
func (node *ListNode) HashPre() bool {
	return node.pre != nil
}

// HashNext  判断当前节点是否存在后继节点
func (node *ListNode) HashNext() bool {
	return node.next != nil
}

// IsNil 判断当前节点是否为空
func (node *ListNode) IsNil() bool {
	return node == nil
}

// Len 返回列表长度
func (list *DoubleList) Len() int {
	return list.len
}

// AddNodeFromHead 从头部开始，指定位置插入节点
func (list *DoubleList) AddNodeFromHead(n int, v string) {
	// 加并发锁
	list.lock.Lock()
	defer list.lock.Unlock()

	// 如果索引超过或者等于列表长度，一定找不到，直接panic即可
	if n >= list.len && n != 0 || n < 0 {
		panic("index out")
	}

	// 找到头节点
	node := list.head
	// 往后遍历拿到第 n + 1个位置的元素
	for i := 1; i <= n; i++ {
		node = node.next
	}

	newNode := new(ListNode)
	newNode.value = v

	// 如果定位到的节点为空，表示当前双端列表为空，需要将新节点设置为新的头结点和尾节点
	if node.IsNil() {
		list.head = newNode
		list.tail = newNode
	} else {
		// 定位到了节点位置，插入该节点的前驱位置即可
		pre := node.pre

		// 如果定位到的节点的前驱节点为空，那么定位到的节点为链表的头节点，需要更换头节点为新的插入节点
		if pre.IsNil() {
			newNode.next = node
			node.pre = newNode
			// 新节点成为头节点
			list.head = newNode
		} else {
			// 将新节点插入到定位到的节点之前
			pre.next = newNode
			newNode.pre = pre


			newNode.next = node
			node.pre = newNode
		}
	}

	// 列表长度 + 1
	list.len = list.len + 1
}


// AddNodeFromTail 从尾部开始指定位置插入节点
func (list *DoubleList) AddNodeFromTail(n int, v string) {
	// 加并发锁
	list.lock.Lock()
	defer list.lock.Unlock()

	// 如果索引超过或者等于列表长度，一定找不到，直接panic
	if n != 0 && n >= list.len {
		panic("index out")
	}

	// 找到尾部
	node := list.tail

	// 往前遍历拿到第 N + 1个位置的元素
	for i := 1; i <= n; i++ {
		node = node.pre
	}

	// 新节点
	newNode := new(ListNode)
	newNode.value = v

	// 如果定位到的节点为空，表示列表为空，将新节点设置为新的头节点和尾节点
	if node.IsNil() {
		list.head = newNode
		list.tail = newNode
	} else {
		// 定位到的节点的后驱节点
		next := node.next

		// 如果定位到的节点的后驱节点为空，那么说明定位到的节点为链表的尾节点，需要更换新的尾节点为当前节点
		if next.IsNil() {
			// 将新节点插入到旧尾节点之后，成为新的尾节点
			node.next = newNode
			newNode.pre = node

			list.tail = newNode
		} else {
			// 将新节点插入到定位的节点之后
			newNode.pre = node
			node.next = newNode

			newNode.next = next
			next.pre = newNode
		}
	}

	// 列表长度 + 1
	list.len = list.len + 1
}

// IndexFromHead 从头部开始获取指定位置的列表节点
func (list *DoubleList) IndexFromHead(n int) *ListNode {
	// 如果索引超过或者等于列表长度，一定找不到，返回空指针即可
	if n >= list.len {
		return nil
	}

	// 获取头节点
	node := list.head

	// 往后遍历拿到第n + 1个位置的节点
	for i := 1; i <= n; i++ {
		node = node.next
	}

	// 此时node就是定位到的目标节点
	return node
}

// IndexFromTail 从尾部开始获取指定位置的列表节点
func (list *DoubleList) IndexFromTail(n int) *ListNode {

	// 如果索引超过或者等于列表长度，一定找不到，返回空指针
	if n >= list.len {
		return nil
	}

	// 获取尾部节点
	node := list.tail

	// 往前遍历拿到目标节点
	for i := 1; i <= n; i++ {
		node = node.pre
	}
	return node
}

// PopFromHead 从头部开始移除并返回某个位置的节点
func (list *DoubleList) PopFromHead(n int) *ListNode {
	// 加并发锁
	list.lock.Lock()
	defer list.lock.Unlock()

	// 索引超过或者等于列表长度，一定找不到，直接返回空指针·
	if n >= list.len {
		return nil
	}
	// 获取头节点
	node := list.head

	// 往后遍历拿到待删除节点
	for i := 1; i <= n; i++ {
		node = node.next
	}

	// 获取节点的前驱节点后后继节点
	preNode := node.pre
	nextNode := node.next

	if preNode.IsNil() && nextNode.IsNil() {
		// 前驱节点和后继节点均为空，说明需要被移除的节点是链表的唯一节点
		list.head = nil
		list.tail = nil
	} else if preNode == nil {
		// 前驱节点为空，说明需要移除的当前的节点是头节点
		list.head = nextNode
		nextNode.pre = nil
	} else if nextNode == nil {
		// 后继节点为空，说明需要移除的当前节点是尾节点
		list.tail = preNode
		preNode.next = nil
	} else {
		preNode.next = nextNode
		nextNode.pre = preNode
	}

	// 节点数量 - 1
	list.len = list.len - 1

	return node
}

// 获取链表头节点
func (list *DoubleList) First() *ListNode {
	return list.head
}

// PopFromTail 从尾部开始移除并返回某个位置的节点
func (list *DoubleList) PopFromTail(n int) *ListNode {

	// 加并发锁
	list.lock.Lock()
	defer list.lock.Unlock()

	// 边界条件判断
	if n >= list.len {
		return nil
	}

	// 定位待删除节点
	node := list.tail

	for i := 1; i <= n; i++ {
		node = node.pre
	}

	preNode := node.pre
	nextNode := node.next

	if preNode.IsNil() && nextNode.IsNil() {
		// 如果前驱节点和后继节点均为空，说明当前待删除的节点就是列表唯一的节点
		list.head = nil
		list.tail = nil
	} else if preNode.IsNil() {
		// 如果待删除节点的前驱节点为空，说明待删除节点是列表的头节点
		list.head = nextNode
		nextNode.pre = nil
	} else if nextNode.IsNil() {
		// 如果待删除节点的后继节点为空，说明待删除节点是该列表的尾节点
		list.tail = preNode
		preNode.next = nil
	} else {
		// 删除中间节点即可
		preNode.next = nextNode
		nextNode.pre = preNode
	}


	// 节点数量 - 1
	list.len = list.len - 1

	return node
}


func main() {

	list := new(DoubleList)
	// 在列表头部插入新元素
	list.AddNodeFromHead(0, "I")
	list.AddNodeFromHead(0, "love")
	list.AddNodeFromHead(0, "you")
	// 在列表尾部插入新元素
	list.AddNodeFromTail(0, "may")
	list.AddNodeFromTail(0, "happy")
	list.AddNodeFromTail(list.Len()-1, "begin second")
	list.AddNodeFromHead(list.Len()-1, "end second")
	// 正常遍历，比较慢，因为内部会遍历拿到值返回
	for i := 0; i < list.Len(); i++ {
		// 从头部开始索引
		node := list.IndexFromHead(i)
		// 节点为空不可能，因为list.Len()使得索引不会越界
		if !node.IsNil() {
			fmt.Println(node.GetValue())
		}
	}
	fmt.Println("----------")
	// 正常遍历，特别快，因为直接拿到的链表节点
	// 先取出第一个元素
	first := list.First()
	for !first.IsNil() {
		// 如果非空就一直遍历
		fmt.Println(first.GetValue())
		// 接着下一个节点
		first = first.GetNext()
	}
	fmt.Println("----------")
	// 元素一个个 POP 出来
	for {
		node := list.PopFromHead(0)
		if node.IsNil() {
			// 没有元素了，直接返回
			break
		}
		fmt.Println(node.GetValue())
	}
	fmt.Println("----------")
	fmt.Println("len", list.Len())

}

























